#pragma once

#include<iostream>
#include<bitset>
#include<string>

using namespace std;

struct BKDRHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (auto ch : str)
        {
            hash = hash * 131 + ch;
        }

        return hash;
    }
};

struct APHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (size_t i = 0; i < str.size(); i++)
        {
            size_t ch = str[i];
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }

        return hash;
    }
};

struct DJBHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 5381;
        for (auto ch : str)
        {
            hash += (hash << 5) + ch;
        }

        return hash;
    }
};


template<size_t N
    , class K = string
    , class Hash1 = BKDRHash
    , class Hash2 = APHash
    , class Hash3 = DJBHash>
class BloomFilter
{
public:
    void set(const K& key)
    {
        size_t hash1 = Hash1()(key) % N;
        _bt.set(hash1);
        
        size_t hash2 = Hash2()(key) % N;
        _bt.set(hash2);

        size_t hash3 = Hash3()(key) % N;
        _bt.set(hash3);

        cout << hash1 << endl;
        cout << hash2 << endl;
        cout << hash3 << endl << endl;
    }

    bool test(const K& key)
    {
        size_t hash1 = Hash1()(key) % N;
        if (!_bt.test(hash1))
            return false;

        size_t hash2 = Hash2()(key) % N;
        if (!_bt.test(hash2))
            return false;

        size_t hash3 = Hash3()(key) % N;
        if (!_bt.test(hash3))
            return false;
        return true;
    }
private:
	bitset<N> _bt;
};
